package LeetCode.interview;

import LeetCode.interview._021_Merge_Two_Sorted_Lists.ListNode;
import util.LogUtils;

/*
 * 
原题

　　Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. 
　　Note: 
　　You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively. 

题目大意

　　给定两个排序的数组，将两个数组进行合并，合并后也是有序的，合并结果存放在nums1中。nums1中有足够的空间容纳nums2。 

解题思路
	法一：
		原地归并排序 @_021_Merge_Two_Sorted_Lists
	法二：
		这样固然没错，但是还有更简洁的方法，而且不用申请新变量。
		算法思想是：
			由于合并后A数组的大小必定是m+n，所以从最后面开始往前赋值，
				先比较A和B中最后一个元素的大小，把较大的那个插入到m+n-1的位置上，再依次向前推。
					如果A中所有的元素都比B小，那么前m个还是A原来的内容，没有改变。
					如果A中的数组比B大的，当A循环完了，B中还有元素没加入A，
						直接用个循环把B中所有的元素覆盖到A剩下的位置。
 * @Date 2017-09-13 15：14
 */
public class _088_Merge_Sorted_Array {

    public _088_Merge_Sorted_Array merge(int[] nums1, int m, int[] nums2, int n) {
    	//eg: m=4, n=4, 最后合并后总长度8,最后一位索引为4+4-1=7
    	int count = m+n-1;
    	m--;
    	n--;
    	//与原地归并排序 一样，从最大的开始填充数组，取两个数组中的较大值
    	while (m>=0 && n>=0)	nums1[count--] = (nums1[m] > nums2[n] ? nums1[m--] : nums2[n--]);
    	while (n>=0)			nums1[count--] = nums2[n--];
    	//遍历：看下结果
//    	traverse(nums1);
        return this;
    }

    
    private void traverse(int[] nums) {
    	for (int i = 0; i < nums.length; i ++) {
    		LogUtils.print(nums[i]);
    	}
//    	LogUtils.br();
//    	while (head != null) {
//    		LogUtils.print(head.val);
//    		head = head.next;
//    	}
    }
    
	
	public static void main(String[] args) {
		_088_Merge_Sorted_Array obj = new _088_Merge_Sorted_Array();
		obj.merge(
				new int[] {2, 3, 4, 5, 0, 0, 0, 0}, 4, 
				new int[] {4, 5, 6, 7}, 4
				);
	}
}
